//
// Created by aquawius on 25-3-12.
//

#ifndef QUICK_SORT
#define QUICK_SORT

#include <algorithm>
#include <iostream>
#include <random>

/** 每次选择一个基准数字，将小于基准数字的放置在左侧，大于的放在右侧，采用分治思想处理剩余的序列，直到数据变为有序
 *  时间复杂度： O(nlogn) = O(n) * O(logn)
 *  空间复杂度： （开辟的栈帧）O(logn)
 *
 *  不稳定
 */

// 优化方式： 1. 因为数据在快速排序的过程中，越来越有序；所以在一定范围内可以使用插入排序。
//          2. 使用几个数字去中间数字的下标作为基准数字
//          3. 随机数法

int partition(int arr[], int begin, int end) // O(n)一次， 二叉树高度是O(log2n)
{
    // 这里取第一个数字作为基准数字   优化2
    int val = arr[begin];

    while (begin < end) {
        // 先右边定位到下标
        while (begin < end && arr[end] >= val) {
            end--;
        }

        if (begin < end) {
            arr[begin] = arr[end];
            begin++;
        }

        while (begin < end && arr[begin] <= val) {
            begin++;
        }

        if (begin < end) {
            arr[end] = arr[begin];
            end--;
        }
    }

    // L == R
    arr[begin] = val;
    return begin;
}

// 快排的递归函数
void quickSort(int arr[], const int begin, const int end)
{
    if (begin >= end) { // 结束的条件
        return;
    }

    // 优化1
    /*
    if (end - begin <= 32) {
        insertSort(arr, begin, end);
    }
    */

    // 在[begin, end]在做一次快排， 快排分割函数独立出来
    int pos = partition(arr, begin, end); // 返回L=R也就是基准数的位置

    quickSort(arr, begin, pos - 1);
    quickSort(arr, pos + 1, end);
}

void quickSort(int arr[], const int size)
{
    quickSort(arr, 0, size - 1);
}

int main(int argc, char** argv)
{
    std::random_device rd;
    std::default_random_engine engine(rd());
    std::uniform_int_distribution<int> dis(0, 100);

    static constexpr int MAX_ARRAY_SIZE = 10;

    const auto arr = new int[MAX_ARRAY_SIZE];

    for (int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        arr[i] = dis(engine);
    }

    std::for_each(arr, arr + MAX_ARRAY_SIZE, [](const int a) { std::cout << a << ' '; });

    std::cout << std::endl;
    quickSort(arr, MAX_ARRAY_SIZE);

    std::for_each(arr, arr + MAX_ARRAY_SIZE, [](const int a) { std::cout << a << ' '; });

    // 释放动态分配的内存
    delete[] arr;

    return 0;
}

#endif